package KMP;

public class demo1 {
    public static void main(String[] args) {
        String str = "abcccffggaaffggggkkkllrrr";
        String sub = "aaffk";
        kmp(str,sub);
    }

    public static void kmp(String str,String sub){
        if (str == null || sub == null){
            System.out.println("str 或者 sub 不合法");
            return;
        }
        if (str.length() == 0 || sub.length() == 0){
            System.out.println(str + " 或者 " + sub + " 长度为 0" );
        }

        //用来记录主串的下标
        int i = 0;
        //记录主串的长度
        int strLen = str.length();

        //用来记录子串的下标
        int j = 0;
        //记录子串的长度
        int subLen = sub.length();

        //next 数组，存放的是子串与主串不适配所需要 j 回溯的索引下标,长度为字串的长度
        int[] next = new int[subLen];
        getNext(next,sub);

        while (i < strLen && j < subLen){
            if ( j == -1 || str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else {
                //当不相同的时候，j 需要回溯到指定的地方
                j = next[j];
            }
        }
        //判断退出循环的原因
        if (j >= subLen){
            System.out.println("找到该主串中子串的位置了:" + (i-j) + " 到 " + (i-1));
        }else {
            System.out.println("没有找到！！！");
        }

    }

    public static void getNext(int[] next,String sub){
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        int len = sub.length();
        while (i < len){
            if (k == -1 || sub.charAt(i-1) == sub.charAt(k)){
                next[i] = k+1;
                i++;
                k++;
            }else {
                //如果不相同，那么会继续接着找，直到相同为止或者k==-1为止
                k = next[k];
            }
        }
    }
}
